<div class="syntax"><pre><span class="c"># safesieve.py</span>
<span class="kn">import</span> <span class="nn">traceback</span>
<span class="k">try</span><span class="p">:</span>
    <span class="kn">import</span> <span class="nn">Numeric</span>
<span class="k">except</span> <span class="ne">ImportError</span><span class="p">:</span>
    <span class="k">print</span> <span class="s">&quot;Sorry, you don&#39;t have the Numeric module installed, and this&quot;</span>
    <span class="k">print</span> <span class="s">&quot;script relies on it.  Please install or reconfigure Numeric&quot;</span>
    <span class="k">print</span> <span class="s">&quot;and try again.&quot;</span>
    <span class="k">raise</span>

<span class="k">def</span> <span class="nf">sieve</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
    <span class="c"># Let&#39;s start at array index 1 instead of 0</span>
    <span class="n">array</span> <span class="o">=</span> <span class="n">Numeric</span><span class="o">.</span><span class="n">zeros</span><span class="p">(</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span>
    <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">):</span>
        <span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">=</span> <span class="n">i</span>
	
    <span class="n">done</span> <span class="o">=</span> <span class="bp">False</span>
    <span class="n">prime</span> <span class="o">=</span> <span class="n">array</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="c"># The number, as well as the index.</span>
    <span class="k">while</span> <span class="n">prime</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">:</span>
	<span class="c"># Index 2 corresponds to the number 2 for this indexing scheme</span>
	<span class="n">index</span> <span class="o">=</span> <span class="n">prime</span>
	<span class="n">index</span> <span class="o">+=</span> <span class="n">prime</span>
	<span class="c"># Mark multiples of prime</span>
	<span class="k">while</span> <span class="n">index</span> <span class="o">&lt;=</span> <span class="n">n</span><span class="p">:</span>
	    <span class="n">array</span><span class="p">[</span><span class="n">index</span><span class="p">]</span> <span class="o">=-</span> <span class="mi">1</span>
            <span class="n">index</span> <span class="o">+=</span> <span class="n">prime</span>
        <span class="c"># Get a new prime</span>
	<span class="n">prime</span> <span class="o">+=</span> <span class="mi">1</span>
	<span class="k">while</span> <span class="n">prime</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">:</span>
	    <span class="k">if</span> <span class="n">array</span><span class="p">[</span><span class="n">prime</span><span class="p">]</span> <span class="o">==</span> <span class="o">-</span><span class="mi">1</span><span class="p">:</span>
                <span class="n">prime</span><span class="o">+=</span><span class="mi">1</span>
            <span class="k">elif</span> <span class="n">prime</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">:</span>
                <span class="k">break</span>

    <span class="c"># Grab all the primes</span>
    <span class="n">primes</span> <span class="o">=</span> <span class="p">[]</span>
    <span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">xrange</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="n">n</span><span class="o">+</span><span class="mi">1</span><span class="p">):</span>
        <span class="k">if</span> <span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">!=</span> <span class="o">-</span><span class="mi">1</span><span class="p">:</span>
            <span class="n">primes</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">array</span><span class="p">[</span><span class="n">i</span><span class="p">])</span>
			
    <span class="k">return</span> <span class="n">primes</span>

<span class="k">def</span> <span class="nf">main</span><span class="p">():</span>
    <span class="k">print</span> <span class="s">&quot;This program computes the number of primes between 1 and n</span><span class="se">\n</span><span class="s">using the Sieve of Erastothenes.&quot;</span>
    <span class="nb">input</span> <span class="o">=</span> <span class="nb">raw_input</span><span class="p">(</span><span class="s">&quot;Enter (n):&quot;</span><span class="p">)</span>
	
    <span class="k">try</span><span class="p">:</span>
        <span class="n">n</span> <span class="o">=</span> <span class="nb">int</span><span class="p">(</span><span class="nb">input</span><span class="p">)</span>
    <span class="k">except</span> <span class="ne">ValueError</span><span class="p">:</span>
        <span class="k">print</span> <span class="s">&quot;You entered:&quot;</span><span class="p">,</span><span class="nb">input</span>
        <span class="k">print</span> <span class="s">&quot;Please enter a positive integer next time.&quot;</span>
        <span class="k">return</span>
		
    <span class="n">primes</span> <span class="o">=</span> <span class="n">sieve</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
    <span class="k">print</span> <span class="s">&quot;There are </span><span class="si">%d</span><span class="s"> primes between 1 and </span><span class="si">%d</span><span class="s">.  They are:&quot;</span> <span class="o">%</span> <span class="p">(</span><span class="nb">len</span><span class="p">(</span><span class="n">primes</span><span class="p">),</span><span class="n">n</span><span class="p">)</span>
    <span class="k">print</span> <span class="n">primes</span>
    <span class="k">return</span>
	
<span class="k">if</span> <span class="n">__name__</span><span class="o">==</span><span class="s">&quot;__main__&quot;</span><span class="p">:</span>
    <span class="n">main</span><span class="p">()</span>
</pre></div>
